package greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author tongchen
 * @create 2023-03-12 14:13
 */
public class LCMP {
    //创建对象信息
    public static class Model{
        int c;
        int p;

        public Model(int c, int p) {
            this.c = c;
            this.p = p;
        }
    }
    //创建小根堆类，为后续小根堆做准备
    public static class LowNum implements Comparator<Model>{

        @Override
        public int compare(Model o1, Model o2) {
            return o1.c-o2.c;
        }
    }
    //创建大跟堆类，为后续大跟堆做准备
    public static class HighNun implements Comparator<Model>{

        @Override
        public int compare(Model o1, Model o2) {
            return o2.p-o1.p;
        }
    }

    /**
     *
     * @param cost 每个项目需要花费的钱
     * @param profit 每个项目能得到的利润
     * @param k 需要做的k个项目
     * @param w 收益
     * @return
     */

    public static int doProgect(int []cost,int[]profit,int k,int w){
        //创建大跟堆和小跟堆
        PriorityQueue<Model> low = new PriorityQueue<>(new LowNum());
        PriorityQueue<Model> high = new PriorityQueue<>(new HighNun());
        //创建项目
        for (int i = 0; i < cost.length; i++) {
            low.add(new Model(cost[i],profit[i]));
        }
        //再次for循环实现取值计算
        for (int i = 0; i <k ; i++) {
            while(!low.isEmpty()&&low.peek().c<=w){
                //把当前能做的项目全拿到获利的堆中
                high.add(low.poll());
            }
            //从获利的堆中不断拿取项目
            if(high.isEmpty()){
                //没有项目直接返回
                return w;
            }
            w+=high.poll().p;
        }
        //全部处理完后取回盈利的钱
        return  w;
    }
}
